package lc;

import java.util.Arrays;

public class Ex279 {
    class Solution1 {
        public int numSquares(int n) {
            int[] f = new int[n + 1];
            f[0] = 0;
            f[1] = 1;
            for (int i = 2; i <= n; i++) {
                int t;
                f[i] = Integer.MAX_VALUE;
                for (int j = 1; (t = i - j * j) >= 0; j++) {
                    f[i] = Math.min(f[i], f[t] + 1);
                }
            }
            return f[n];
        }
    }

    //利用完全背包的解法
    class Solution {
        public int numSquares(int n) {
            int[] f = new int[n + 1];

            Arrays.fill(f, Integer.MAX_VALUE);
            f[0] = 0;
            for (int i = 1; i * i <= n; i++) {
                f[i * i] = 1;
            }
            for (int i = 2; i <= n; i++) {
                if (f[i] == 1) {
                    continue;
                }
                for (int j = 1; j * j <= i; j++) {
                    int t = i - j * j;
                    if (f[t] != Integer.MAX_VALUE) {
                        f[i] = Math.min(f[t], f[t] + 1);
                    }
                }
            }
            return f[n];
        }
    }
}
